package zuochengyun.chapter9;

//在有序旋转数组中找到最小值
public class MinValueOfRotatedSortArray {

	//Testcase
	public static void main(String[] args) {
		MinValueOfRotatedSortArray object = new MinValueOfRotatedSortArray();
		int[] arr = {0,2,2,3,5,0,0,0,0,0};
		int[] arr1 = {0,0,0,1,0};
		int[] arr2 = {0,1,0,0,0};
		int[] arr3 = {3,6, 8, 10, 2, 3};
		int[] arr4 = {3,9, 0, 1, 2, 3};
		System.out.println(object.getMin2(arr));
		System.out.println(object.getMin2(arr1));
		System.out.println(object.getMin2(arr2));
		System.out.println(object.getMin2(arr3));
		System.out.println(object.getMin2(arr4));
	}
	
	
	
	//数组中的元素不会重复
	public int getMin(int[] arr){
		int low = 0;
		int high = arr.length - 1;
		int mid = 0;
		while(low < high){
			if(low == high - 1){
				break;
			}
			if(arr[low] < arr[high]){
				return arr[low];
			}
			if(arr[low] > arr[mid]){
				high = mid;
			}
			if(arr[mid] > arr[high]){
				low = mid;
			}
		}
		return arr[low];
	}
	
	//数组中的元素会重复
	public int getMin2(int[] arr){
		int low = 0;
		int high = arr.length - 1;
		int mid = 0;
		//由于这个二分的时候不是mid - 1， mid + 1,所以如果low = high - 1的时候mid会等于low
		//会造成死循环的出现，所以我们此时就退出了，在返回的时候进行判断即可
		while(low < high){
			if(low == high - 1){
				break;
			}
			if(arr[low] < arr[high]){
				return arr[low];
			}
			mid = (high + low) / 2;
			if(arr[low] > arr[mid]){
				high = mid;
				continue;
			}
			if(arr[mid] > arr[high]){
				//之前这里一直写的low = mid + 1
				//后来发现这样是不行的，比如0 2 2 3 5 0 0 0 0 0
				//初始low = 0，high = 9
				//如果low = mid + 1， 那么会变成low = 5，high = 9，此时无法获取到正确的结果
				low = mid;
				continue;
			}
			//如果以上情况都不符合，说明arr[low] >= arr[high], arr[low] <= arr[mid], arr[mid] <= arr[high]
			//所以只有arr[low] == arr[mid] == arr[high]
			//此时仍然可以使用二分法
			while(low < mid){
				if(arr[low] == arr[mid]){
					low++;
				}else if(arr[low] < arr[mid]){
					return arr[low];
				}else{
					high = mid;
					break;
				}
			}
		}
		System.out.println("low: " + low + " " + arr[low] + " high: " + high + " "+ arr[high]);
		return Math.min(arr[high], arr[low]);	//此时判断哪个小就返回哪个即可
	}
}
